#!/usr/bin/python
# Filename: Queue.py

class SQueue:
    '''Sequential Queue'''
    def __init__(self, max_length=20):
        self._items = [None] * max_length
        self.max_length = max_length
        self.length = 0
        self._head = 0
        self._tail = -1

    def __str__(self):
        # caution: _tail+1=_head can be empty or full,
        # _tail=_head when empty or full is also ok.
        if self.length == 0: return str([])
        elif self._head <= self._tail: return str(self._items[self._head:self._tail+1])
        else: return str(self._items[self._head:]+self._items[:self._tail+1])

    def is_empty(self):
        return self.length == 0

    def is_full(self):
        return self.length == self.max_length

    def en_queue(self, value):
        '''Append value to the end of queue, if the queue is not full'''
        if self.is_full(): return False
        self._tail += 1
        self._tail %= self.max_length
        self._items[self._tail] = value
        self.length += 1
        return True

    def de_queue(self):
        '''Get value from the beginning of queue, if the queue is not empty'''
        if self.is_empty(): return None
        value = self._items[self._head]
        self._head +=1
        self._head %= self.max_length
        self.length -= 1
        return value

    def get_first(self):
        '''Get value from the beginning of queue, if the queue is not empty'''
        if self.is_empty(): return None
        value = self._items[self._head]
        return value

    def clear(self):
        self._tail = self._head - 1
        self._tail %= self.max_length
        self.length = 0
        return True


from LinkedList import Node


class Queue:
    '''Linked Queue'''
    def __init__(self):
        self.length = 0
        self.head = None
        self.tail = None

    def __str__(self):
        string = '['
        curr_node = self.head
        while curr_node:
            string += (str(curr_node) + ", ")
            curr_node = curr_node.next
        string += ']'
        return string

    def is_empty(self):
        return (self.length == 0)

    def en_queue(self, value):
        '''Append value to the end of queue'''
        node = Node(value)
        if self.head:
            self.tail.next = node
        else:
            self.head = node
        self.tail = node
        self.length += 1

    def de_queue(self):
        '''Get first value of queue, when not empty'''
        if self.is_empty(): return None

        node = self.head
        self.head = self.head.next
        self.length -= 1
        if self.is_empty(): self.tail = None

        value = node.value
        del node
        return value

    def get_first(self):
        '''Get first value of queue, when not empty'''
        if self.is_empty(): return None
        else: return self.head.value

    def clear(self):
        curr_node = self.head
        while curr_node:
            node = curr_node
            curr_node = curr_node.next
            del node
        self.head = None
        self.tail = None
        self.length = 0
        return True


if __name__ == "__main__":
    def test_queue():
        print "Queue is under testing..."
        q = Queue()
        for i in range(0, 25):
            print "q.en_queue():", q.en_queue(i), q
        for i in range(0, 10):
            print "q.de_queue():", q.de_queue(), q
        for i in range(0, 10):
            print "q.en_queue():", q.en_queue(i), q
        print "clear queue:", q.clear(), q
        for i in range(0, 5):
            print "q.de_queue():", q.de_queue(), q
        for i in range(0, 5):
            print "q.en_queue():", q.en_queue(i), q
        for i in range(0, 5):
            print "q.get_first():", q.get_first(), q

    test_queue()
    
